package 链表.回文链表;


import static java.util.Collections.reverse;

/**
 * @Program:IntelliJ IDEA
 * @description:
 * @author:香蕉你个啵娜娜 l.h-p@qq.com
 * @create:2023-01-05 21:06
 **/

public class Solution {
    public boolean isPalindrome(ListNode head){
        ListNode fast = head, slow = head;
        // 通过快慢指针找到中点
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        // 如果fast不为空，说明链表的长度是奇数个
        if (fast != null){
            slow = slow.next;
        }
        // 反转后半部分链表
        slow = reverse(slow);
        fast  = head;
        while (slow != null){
            // 然后比较，判断节点值是否相等
            if (fast.val != slow.val){
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null){
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}
